<!-------- @HEADER
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 !  Zoltan Toolkit for Load-balancing, Partitioning, Ordering and Coloring
 !                  Copyright 2012 Sandia Corporation
 !
 ! Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
 ! the U.S. Government retains certain rights in this software.
 !
 ! Redistribution and use in source and binary forms, with or without
 ! modification, are permitted provided that the following conditions are
 ! met:
 !
 ! 1. Redistributions of source code must retain the above copyright
 ! notice, this list of conditions and the following disclaimer.
 !
 ! 2. Redistributions in binary form must reproduce the above copyright
 ! notice, this list of conditions and the following disclaimer in the
 ! documentation and/or other materials provided with the distribution.
 !
 ! 3. Neither the name of the Corporation nor the names of the
 ! contributors may be used to endorse or promote products derived from
 ! this software without specific prior written permission.
 !
 ! THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
 ! EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 ! IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 ! PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
 ! CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 ! EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 ! PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 ! PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 ! LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 ! NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 ! SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 !
 ! Questions? Contact Karen Devine	kddevin@sandia.gov
 !                    Erik Boman	egboman@sandia.gov
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 ! @HEADER
-------> 
<!DOCTYPE html PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
  <meta http-equiv="Content-Type"
 content="text/html; charset=iso-8859-1">
  <meta name="GENERATOR"
 content="Mozilla/4.7 [en] (X11; U; SunOS 5.7 sun4u) [Netscape]">
  <meta name="sandia.approval_type" content="formal">
  <meta name="sandia.approved" content="SAND2007-4748W">
  <meta name="author" content="Zoltan PI">

  <title>Zoltan User's Guide: RCB</title>
</head>
<body bgcolor="#ffffff">
<div align="right"><b><i><a href="ug.html">Zoltan User's Guide</a>&nbsp;
|&nbsp; <a href="ug_alg_rib.html">Next</a>&nbsp; |&nbsp; <a
 href="ug_alg_geom.html">Previous</a></i></b></div>
<h2>
<a name="RCB"></a>Recursive Coordinate Bisection (RCB)</h2>
An implementation of Recursive Coordinate Bisection (RCB) due to Steve
Plimpton of Sandia National Laboratories is included in Zoltan.
RCB was first proposed as a static load-balancing algorithm by
<a href="ug_refs.html#berger">Berger
and Bokhari</a>, but is attractive as a dynamic load-balancing
algorithm
because it implicitly produces incremental partitions. In RCB, the
computational
domain is first divided into two regions by a cutting plane orthogonal
to one of the coordinate axes so that half the work load is in each of
the sub-regions. The splitting direction is determined by computing in
which coordinate direction the set of objects is most elongated, based
upon the geometric locations of the objects. The sub-regions are then
further
divided by recursive application of the same splitting algorithm until
the number of sub-regions equals the number of processors.  Although this
algorithm was first devised to cut into a number of sets which is a power
of two, the set sizes in a particular cut needn't be equal. By adjusting
the part sizes appropriately, any number of equally-sized sets can
be created. If the parallel machine has processors with different
speeds,
sets with nonuniform sizes can also be easily generated. The Zoltan
implementation
of RCB has several parameters which can be modified by the <b><a
 href="ug_interface_init.html#Zoltan_Set_Param">Zoltan_Set_Param</a></b>
function. A recent feature is that RCB allows multiple weights; that
is, one can balance with respect to several load criteria
simultaneously.
Note that there is no guarantee that a desired load balance tolerance
can be achieved using RCB, especially in the multiconstraint case.<br>
<p>
Information about the sub-regions generated by RCB can be obtained by an
application through calls to 
<a href="#Zoltan_RCB_Box"><b>Zoltan_RCB_Box</b></a>.  This function is not
required to perform load balancing; it only provides auxiliary information
to an application.
<br>&nbsp;
<br>
&nbsp;
<table width="100%" nosave="">
  <tbody>
    <tr>
      <td valign="top"><b>Method String:</b></td>
      <td><b>RCB</b></td>
    </tr>
    <tr>
      <td><b>Parameters:</b></td>
      <td><br>
      </td>
    </tr>
    <tr>
      <td valign="top">&nbsp;&nbsp;&nbsp; <i>RCB_OVERALLOC</i></td>
      <td>The amount by which to over-allocate temporary storage arrays
for objects
within the RCB algorithm when additional storage is due to changes in
processor
assignments.&nbsp; <br>
1.0 = no extra storage allocated; 1.5 = 50% extra storage; etc.</td>
    </tr>
    <tr>
      <td valign="top"><i>&nbsp;&nbsp;&nbsp; RCB_REUSE</i></td>
      <td>Flag to indicate whether to use previous cuts as initial
guesses for
the current RCB invocation.&nbsp; <br>
0 = don't use previous cuts; 1 = use previous cuts.</td>
    </tr>
    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> RCB_OUTPUT_LEVEL</i></td>
      <td>Flag controlling the amount of timing and diagnostic output
the routine
produces.&nbsp; <br>
0 = no output; 1 = print summary; 2 = print data for each processor.</td>
    </tr>
    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> CHECK_GEOM</i></td>
      <td>Flag controlling the invocation of input and output error
checking.&nbsp; <br>
0 = don't do checking; 1 = do checking.</td>
    </tr>
    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> KEEP_CUTS</i></td>
      <td>Should information about the cuts determining the RCB
decomposition
be retained? It costs a bit of time to do so, but this information is
necessary
if application wants to add more objects to the decomposition via calls
to <b><a href="ug_interface_augment.html#Zoltan_LB_Point_PP_Assign">Zoltan_LB_Point_PP_Assign</a></b>
or to <b><a href="ug_interface_augment.html#Zoltan_LB_Box_PP_Assign">Zoltan_LB_Box_PP_Assign</a></b>.&nbsp;
      <br>
0 = don't keep cuts; 1 = keep cuts.</td>
    </tr>
<tr>
<td VALIGN=TOP NOSAVE>&nbsp;&nbsp;<a name="AVERAGE_CUTS"></a><i> AVERAGE_CUTS</i></td>

<td>When set to one, coordinates of RCB cutting planes are computed to be the 
average of the coordinates of the closest object on each side of the cut.
Otherwise, coordinates of cutting planes may equal those of one of the 
closest objects.
<br>0 = don't average cuts; 1 = average cuts.</td>
</tr>

    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> RCB_LOCK_DIRECTIONS</i></td>
      <td>Flag that determines whether the order of the directions of
the cuts is kept
constant after they are determined the first time RCB is called.&nbsp; <br>
0 = don't lock directions; 1 = lock directions.</td>
    </tr>
    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> RCB_SET_DIRECTIONS</i></td>
      <td>If this flag is set, the order of cuts is changed so that all
of the cuts
in any direction are done as a group. The number of cuts in each
direction is
determined and then the value of the parameter is used to determine the
order
that those cuts are made in. When 1D and 2D problems are partitioned,
the
directions corresponding to unused dimensions are ignored.&nbsp; <br>
0 = don't order cuts; 1 = xyz; 2 = xzy; 3 = yzx; 4 = yxz; 5 = zxy; 6 =
zyx;</td>
    </tr>
    <tr>
      <td valign="top" nosave="">&nbsp;&nbsp;<i> RCB_RECTILINEAR_BLOCKS</i></td>
      <td>Flag controlling the shape of the resulting regions. If this
option is
specified, then when a cut is made, all of the dots located on the cut
are
moved to the same side of the cut. The resulting regions are then
rectilinear. When these dots are treated as a group, then the resulting
load balance may not be as good as when the group of dots is split by
the
cut.&nbsp; <br>
0 = move dots individually; 1 = move dots in groups.<br>
      </td>
    </tr>
<tr>
<td VALIGN=TOP NOSAVE>&nbsp;&nbsp;<i> REDUCE_DIMENSIONS</i></td>
<td>
When a 3 dimensional geometry is almost flat, it may make more
sense to treat it as a 2 dimensional geometry when applying the RCB
algorithm.  In this case, a 2 dimensional RCB calculation is applied to a plane 
that corresponds with the geometry. (This results in cuts that, while 
still orthogonal, may no longer be axis aligned.)
If this parameter is set to <B>1</B>, a 3 dimensional
geometry will be treated as 2 dimensional if it is very flat, 
or 1 dimensional if it is very thin.  A 2 dimensional geometry will
be treated as 1 dimensional if it is very thin.
</td>
</tr>
<tr>
<td VALIGN=TOP NOSAVE>&nbsp;&nbsp;<i> DEGENERATE_RATIO</i></td>
<td>
If the <B>REDUCE_DIMENSIONS</B> parameter is set, then this parameter
determines when a geometry is considered to be degenerate.  
A bounding box which is oriented to the geometry is constructed, and
the lengths of its sides are tested against a ratio of 1 : <B>DEGENERATE_RATIO</B>.
</td>
</tr>
<td VALIGN=TOP NOSAVE>&nbsp;&nbsp;<i> RCB_RECOMPUTE_BOX</i></td>

<td>Flag indicating whether the bounding box of set of parts is
recomputed at each level of recursion.  By default, the longest direction
of the bounding box is cut during bisection.  Recomputing the bounding
box at each level of recursion can produce more effective cut directions
for unusually shaped geometries; the computation does, however, take
additional time and communication, and may cause cut directions to
vary from one invocation of RCB to the next.
<br>0 = don't recompute the bounding box; 1 = recompute the box.</td>
</tr>

    <tr>
      <td valign="top"><i>&nbsp;&nbsp; OBJ_WEIGHTS_COMPARABLE</i><br>
      </td>
      <td valign="top">In the multiconstraint case, are
the object weights comparable? Do they have the same units and is the
scaling meaningful? For example, if the jth weight corresponds to the
expected time in phase j (measured in seconds), set this parameter to
1. (0 = incomparable, 1 =&nbsp; comparable)<br>
      </td>
    </tr>
    <tr>
      <td valign="top"><i>&nbsp;&nbsp; RCB_MULTICRITERIA_NORM<br>
      </td>
      <td valign="top">Norm used in multicriteria
algorithm; this determines how to balance the different weight
constraints. Valid values are 1,2, and 3. Roughly, if the weights
correspond to different phases, then the value 1 (1-norm) tries to
minimize the&nbsp; total time (sum over all phases) while the value 3
(max-norm) attempts to minimize the worst imbalance in any phase. The
2-norm does something in between. Try a different value if you're
not happy with the balance. <br>
      </td>
    </tr>
    <tr>
      <td valign="top"><i>&nbsp;&nbsp; RCB_MAX_ASPECT_RATIO</i><br>
      </td>
      <td valign="top">Maximum allowed ratio between
the largest and smallest side of a subdomain. Must be &gt; 1. <br>
      </td>
    </tr>
    <tr>
      <td valign="top"><b>Default:</b></td>
      <td><br>
      </td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_OVERALLOC</i> = 1.2</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_REUSE</i> = 0</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_OUTPUT_LEVEL</i> = 0</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>CHECK_GEOM</i> = 1</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>KEEP_CUTS</i> = 0</td>
    </tr>
<tr>
<td></td>
<td><i>AVERAGE_CUTS</i> = 0</td>
</tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_LOCK_DIRECTIONS</i> = 0</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>REDUCE_DIMENSIONS</i> = 0</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>DEGENERATE_RATIO</i> = 10</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_SET_DIRECTIONS</i> = 0</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><i>RCB_RECTILINEAR_BLOCKS</i> = 0</td>
    </tr>
<tr>
<td></td>
<td><i>RCB_RECOMPUTE_BOX</i> = 0</td>
</tr>
    <tr>
      <td valign="top"><br>
      </td>
      <td valign="top"><i>OBJ_WEIGHTS_COMPARABLE</i> = 0<br>
      </td>
    </tr>
    <tr>
      <td valign="top"><br>
      </td>
      <td valign="top"><i>RCB_MULTICRITERIA_NORM</i> = 1<br>
      </td>
    </tr>
    <tr>
      <td valign="top"><br>
      </td>
      <td valign="top"><i>RCB_MAX_ASPECT_RATIO</i> = 10<br>
      </td>
    </tr>
    <tr>
      <td valign="top"><b>Required Query Functions:</b></td>
      <td><br>
      </td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><b><a href="ug_query_lb.html#ZOLTAN_NUM_OBJ_FN">ZOLTAN_NUM_OBJ_FN</a></b></td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><b><a href="ug_query_lb.html#ZOLTAN_OBJ_LIST_FN">ZOLTAN_OBJ_LIST_FN</a></b>
</td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td><b><a href="ug_query_lb.html#ZOLTAN_NUM_GEOM_FN">ZOLTAN_NUM_GEOM_FN</a></b></td>
    </tr>
    <tr>
      <td><br>
      </td>
      <td> <b><a href="ug_query_lb.html#ZOLTAN_GEOM_MULTI_FN">ZOLTAN_GEOM_MULTI_FN</a></b>
or <b><a href="ug_query_lb.html#ZOLTAN_GEOM_FN">ZOLTAN_GEOM_FN</a></b>
      </td>
    </tr>
  </tbody>
</table>
<p>
<HR WIDTH="100%">
<A NAME="Zoltan_RCB_Box"></A>
<HR WIDTH="100%">
<TABLE WIDTH="100%" NOSAVE >
<TR NOSAVE>
<TD VALIGN=TOP NOSAVE>C:</TD>

<TD WIDTH="85%">
int <B>Zoltan_RCB_Box</B> (
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;struct <B>Zoltan_Struct</B> *<I> zz</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int <I>part</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int <I>*ndim</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*xmin</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*ymin</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*zmin</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*xmax</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*ymax</I>,
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double <I>*zmax</I>);
</TD>
</TR>

<TR NOSAVE>
<TD VALIGN=TOP WIDTH="15%" NOSAVE>FORTRAN:</TD>

<TD> FUNCTION <B>Zoltan_RCB_Box</B>(<I>zz, part,ndim, xmin, ymin, zmin, 
xmax, ymax, zmax</I>)&nbsp;
<BR> INTEGER(Zoltan_INT) :: Zoltan_RCB_Box
<BR> TYPE(Zoltan_Struct), INTENT(IN) :: zz
<BR> INTEGER(Zoltan_INT), INTENT(IN) :: part
<BR> INTEGER(Zoltan_INT), INTENT(OUT) :: ndim
<BR> REAL(Zoltan_DOUBLE), INTENT(OUT) :: xmin, ymin, zmin, xmax, ymax, zmax
</TD>
</TR>
</TABLE>
<HR WIDTH="100%">
In many settings, it is useful to know a part's bounding box 
generated by RCB.  This bounding box describes the region of space
assigned to a given part.
Given an RCB decomposition of space and a part number,
<B>Zoltan_RCB_Box</b> returns the lower
and upper corners of the region of space assigned to the part.
To use this routine, the parameter <B>KEEP_CUTS</B>
must be set to TRUE when the decomposition is generated. This parameter
will cause the sequence of geometric cuts to be saved, which
is necessary for <B>Zoltan_RCB_Box</B> to do its job.
<BR>&nbsp;

<TABLE WIDTH="100%" >
<TR>
<TD VALIGN=TOP WIDTH="20%"><B>Arguments:</B></TD>
<td WIDTH="80%"></td>
</TR>

<TR>
<TD><I>&nbsp;&nbsp;&nbsp; zz</I></TD>

<TD>Pointer to the Zoltan structure created by <B><A HREF="ug_interface_init.htm
l#Zoltan_Create">Zoltan_Create</A></B>.</TD>
</TR>

<TR>
<TD><I>&nbsp;&nbsp;&nbsp; part</I></TD>

<TD>Part number of part for which the bounding box should be returned.
</td>
</TR>

<TR>
<TD><I>&nbsp;&nbsp;&nbsp; ndim</I></TD>

<TD>Upon return, the number of dimensions in the partitioned geometry.
</td>
</TR>

<TR>
<TD VALIGN=TOP><I>&nbsp;&nbsp; xmin, ymin, zmin</I></TD>

<TD>Upon return, the coordinates of the lower extent of bounding box 
for the part. 
If the geometry is two-dimensional, <i>zmin</i> is -DBL_MAX.
If the geometry is one-dimensional, <i>ymin</i> is -DBL_MAX.
</TD>
</TR>
<TR>
<TD VALIGN=TOP><I>&nbsp;&nbsp; xmax, ymax, zmax</I></TD>

<TD>Upon return, the coordinates of the upper extent of bounding box 
for the part. 
If the geometry is two-dimensional, <i>zmax</i> is DBL_MAX.
If the geometry is one-dimensional, <i>ymax</i> is DBL_MAX.
</TD>
</TR>

<TR>
<TD><B>Returned Value:</B></TD>

<TD></TD>
</TR>

<TR>
<TD VALIGN=TOP>&nbsp;&nbsp;&nbsp; int</TD>

<TD><A HREF="ug_interface.html#Error Codes">Error code</A>.</TD>
</TR>
</table>

<p>

<hr WIDTH="100%">[<a href="ug.html">Table of Contents</a>&nbsp; | 
<a href="ug_alg_rib.html">Next:&nbsp; Recursive Inertial Bisection (RIB)</a>
|&nbsp; <a href="ug_alg_geom.html">Previous:&nbsp; Geometric (Coordinate-based) Partitioners</a>&nbsp; |&nbsp; <a href="https://www.sandia.gov/general/privacy-security/index.html">Privacy and Security</a>]
</body>
</html>
